\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\author{Alex Masson}
\title{TD-Securite et Protocol}
\begin{document}
\maketitle
\newpage
\section{TD 1}
\paragraph{Exercice 1}

dechiffrer VXOSKXU -> SULPHUR -> PRIMERO -> MOFJBOL. 

\paragraph{cryptanalyse}
force brut : on essaye les 26 decalages\\
analyse de fréquence, on repère la lettre la plus fréquente et on l'identifie avec la lettre E -> on a identifié le décalage\\
si l'espace est chiffrée, mes "mots" du texte chiffré ne correspondent plus aux mots du texte original, on ne peux plus identifié les petit mot (comme "à" dans la langue française)\\\\
On chiffre avec $0\leq k\leq 26$\\
du coup déchiffrer reviens a chiffre une autre fois avec k' = -k mod 26\\\\
ROT13 est particulier car sa clé est 13 donc sa clé inverse est aussi 13 donc chiffrer ou déchiffrer ROT13 c’est le même. En général, l'algo de chiffrement/déchiffrement par décalage est le même , juste la clé change.

\paragraph{Exercice 2}
chiffre de Vigenère, 
on a donc une cle CLEF et une phrase TEXTEACHIFFRER, pour chaque lettre on fais un décalage de césar de clé l'indice de la lettre correspondante dans la clé

dechiffrer K = LO, txt = GODMQWWSECYNPFZGTL\\

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
g & o & d & m & q & w & w & s & e & c & y & n & p & f & z & g & t & l \\ 
\hline 
6 & 14 & 3 & 12 & 16 & 22 & 22 & 18 & 4 & 2 & 24 & 13 & 15 & 5 & 25 & 6 & 19 & 11 \\ 
\hline 
p & m & p & m & p & m & p & m & p & m & p & m & p & m & p & m & p & m \\ 
\hline 
15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 & 15 & 12 \\ 
\hline 
21 & 0 & 18 & 24 & 5 & 8 & 11 & 4 & 19 & 14 & 13 & 25 & 4 & 17 & 14 & 18 & 8 & 23 \\ 
\hline 
v & a & s & y & f & i & l & e & t & o & n & z & e & r & o & s & i & x \\ 
\hline 
\end{tabular}\\ 
on a un texte chiffré, on connais la longueur L de la clé.
donc toutes les lettre a la position I modulo L sont cryptés avec la même lettre de la clé qui est la lettre d'indice i de la clé. donc chacun de ces ensemble de lettre sont chiffré avec un décalage mono-alphabétique. sur chancun des $t^i$ sous ensemble, on  cherche la letre la plus frequente, et on en deduit le decalage pour chaque sous ensemble, et du coup la clé, ensuite il est facile de calculer la clé inverse et de re chiffrer pour retrouver le texte.

\paragraph{On veux déterminer la taille de la clé}
\begin{itemize}
\item[Méthode 1] On chercher dans le texte des groupes de lettres qui se répètent. On va supposer que cela correspond au meme texte clair -> on a une répétition dans le texte clair. si on note $\Delta$ la longueur de la répétition, on peux donc supposer sur $\Delta$ que c'est un multiple de la taille L de la clé.\\
On à identifie plusieurs répétitions : $\Delta_1,\Delta_2,...,\Delta_n$. on chercher pour tout $\Delta_i$ leur PGCD. et on applique la méthode ou on connais la taille de la clé.
Mais on émet beaucoup d'hypothèse, on est pas sur qu'elles soient correctes., L n'est pas forcément bon.

\item[Methode 2] Indice de coincidence $IC =\sum_{L=a}^z \frac{n_l(n_l-1)}{n(n-1)}$, où n ets la taille totale tu texte , $n_l$ est le nombre d'occurences de la lettre l dans le texte.
\item Plus l'IC est élevé, plus on est proche d'un texte en langue naturelle chiffré par une substitution mono-alphabetique.
\item[Remarque] il ne tiens compte que de la distribution des lettre set pas des lettres elles même, l'IC est invariant par chiffrage mono-alphabétique. Donc si un texte à été chiffré par une substitution mono-alphabétique, son IC est le meme que celui du texte clair, qui lui est un texte en langue naturelle, ayant un IC élevé
\item[Idée] Utiliser l'IC pour détecter les chiffrement mono-alphabétique, IC élevé = chiffrement mono-alphabétique
\item Pour L = 1,2,... , on découpe T en pleins de sous-ensemble. ON calcule l'IC sur tous les sous-ensemble, si tous les $IC_i$ sont élevés , on peut prendre L comme taille de clé.
\item[Fluctutation]
\begin{itemize}
\item[élevé] entre 0.07 et 0.08
\item[faible] entre 0.03 et 0.04
\end{itemize}
\item[explication] Ce que représente l'IC : mesure simple des "répétitions" de lettres dans un texte. On tire aléatoirement 2 lettres dans T, $X,Y \in \Sigma = \{a..z\}$\\
$P_i[X=Y]=P_i[\bigsqcup_{L\in \Sigma} X=L,Y=L] = \sum_{l\in \Sigma} P_i[X=l \bigcap Y=l]$\\$P_i[X=l \bigcap Y=l]=\frac{nb pairs (l,l) n_l parmis 2}{n parmis 2 (nombre total de paires)} $\\$=\frac{n_l(n_l-1)}{n(n-1)}$
\item[Français] si on note $f_l$ la fréquence de la lettre l, en français IC =  $\sum_{l\in \Sigma} \simeq 0.076$
\end{itemize}

\subsection{XOR}
on remarque que l'opération XOR $\oplus$ est commutative \\
chiffrement  par $\oplus$ :\\
Cle :     011011 \\
message : 001110
cle $\oplus$ message = 010101\\
Aussi si on repasse le message chiffré dans le XOR, alors on retrouve le message, donc le déchiffrement est plutot easy \\
$C(M) = M \oplus K$\\
$D(M) = M \oplus K$\\
$D(C)= (M \oplus K) \oplus K$ Associatif\\
$D(C) = M \oplus (K \oplus K)$ or $X \oplus X = \perp$
$D(C) = M \oplus \perp = M$ Car $X \oplus \perp = X$

\begin{tabular}{|c|c|c|c|c|}
\hline 
a & b & c & (a xor b) xor c & a xor (b xor c) \\ 
\hline 
0 & 0 & 0 & 0 & 0 \\ 
\hline 
0 & 0 & 1 & 1 & 1 \\ 
\hline 
0 & 1 & 0 & 1 & 1 \\ 
\hline 
0 & 1 & 1 & 0 & 0 \\ 
\hline 
1 & 0 & 0 & 1 & 1 \\ 
\hline 
1 & 0 & 1 & 0 & 0 \\ 
\hline 
1 & 1 & 0 & 0 & 0 \\ 
\hline 
1 & 1 & 1 & 1 & 1 \\ 
\hline 
\end{tabular} 
On connait la taille de la clef  |k| de la clef.\\
on connais une partie $M_0$ du message clair de taille |$M_0$| = |k|\\
on note $C_0$ de la partie correspondante dans le message crypté\\on sais $C_0 = M_0 \oplus K$\\
$M_0 \oplus C_0 = M_0 \oplus M_0 \oplus K$ \\ $= 0 \oplus K$\\$= K$

\textbf{On appelle se type d'attaque une attaque à texte clair connu!!}

\paragraph{Exercice 4}
\textbf{Question 1} : quelles sont les difficultés de mise en place du message? \\
La clé doit etre de la meme taille que le message, or les message sont tres long, deplus il faut connaitre la taille du message à l'avance

\paragraph{Exercice 5}
Arithmétique modulo B (b : base)\\
On note :  \\
\begin{itemize}
\item $X \equiv Y$ $mod$ $b$
\item $X \equiv Y [b]$
\item $X =_{/b}Y$
\end{itemize}

\textbf{Vraie égalité}\\
\textbf{def : } $\bar{a} = ${$a+kb, k\in Z$ }\\
$x =_{/b} y \Leftrightarrow x = y+kb \Leftrightarrow x \in \bar{y} \Leftrightarrow \bar{x} = \bar{y}$\\

Dans $\bar{a}$ il y a un unique élément $0 \leq \dot{a} \leq b$\\
Cet élément est le reste dans la division euclidienne de a par b.\\
$x =_{/b} y \Leftrightarrow \dot{x} = \dot{y} \Leftrightarrow$ x et y ont le meme reste dans la division euclienne par b\\
On définit a\%b le reste .\\
$x =_{/b} y \Leftrightarrow x\%b = y\%b$\\

\textbf{hill}\\
clé k =\\
$\begin{matrix}
2 & 1 \\ 
1 & 2
\end{matrix} $
\\
Message = 22,3,4,18,12,13\\
M=
$\begin{array}{ccc}
22 & 4 & 12 \\ 
3 & 18 & 13
\end{array}$ \\ C= K x M /!/ sens!!\\

$\begin{pmatrix}
2 & 1 \\ 
1 & 2

\end{pmatrix} $ $\begin{pmatrix}
21 & 0 & 11 \\ 
2 & 14 & 12
\end{pmatrix} $

\paragraph{Déchiffrement de hills}
on Connais C0 une partie de la clé, et M0 une partie de meme rang (pas de décalage) du message chiffré, \\on sais  : c0 = K.M0\\
On chercher $k^{-1}$ pour dechiffrer \\
$K^{-1} C_0 = K^{-1}.K.M_0 = M_0$\\
$K^{-1}.C_0.C_0^{-1} = K^{-1} = M_0.C_0^{-1}$ /!/ sens!!\\
\textbf{Objectif} trouver $C_0$
det $c_0 = 7*18-5*21$ car $ad-bc$ pour la matrice $\begin{pmatrix}
a & b \\ 
c & d
\end{pmatrix} $\\
en dimension 2 si M = $\begin{pmatrix}
a & b \\ 
c & d
\end{pmatrix} $
et M inversible alors $M^{-1}$ = $(det M)^{-1} \begin{array}{cc}
d & -b \\ 
-c & a
\end{array}$ 
on peut donc trouver $C^{-1}$\\
on sais que $K^{-1} = M_0 . C_0^{-1}$ on peut donc trouver $K^{-1}$ 
\\
Un fois $K^{-1}$ en poche , on peut dechiffrer le message crypté
\paragraph{exo 5 question  4 }
Tout chiffrement par bloc basé sur des combinaisons linéaires peut etre vu comme du hill avec k la matrice des combinaisons-> vulnérable aux attaques par texte clair

\section{TD1 - Exercice 6}
attention base 27 \\
C = CUJIRTREOZQBFHAEJP\\
M = DEBUT$\_$?????????FIN\\
coup de bol ça se coupe bien, -> on attaque
M0  = $\begin{pmatrix}
3 & 20 & 5 \\ 
4 & 19 & 8 \\ 
1 & 26 & 13
\end{pmatrix} $

nature du texte en clair connu \\
c0 = $\begin{array}{ccc}
2 & 8 & 4 \\ 
20 & 17 & 9 \\ 
9 & 19 & 15
\end{array} $\\
$K^{-1} = M_0 .c_0^{-1}$

Méthode 1 \\
$\begin{pmatrix}
a & d & g \\ 
b & e & h \\ 
c & f & i
\end{pmatrix} $ = \textbf{+}a.$\begin{pmatrix}
e & h \\ 
f & i
\end{pmatrix} $ \textbf{-}b.$\begin{pmatrix}
d & g \\ 
f & i
\end{pmatrix} $ \textbf{+}c.$\begin{pmatrix}
d & g \\ 
e & h
\end{pmatrix} $\\ 
\textbf{Inverser $C_0$}
\begin{itemize}
\item[1] Pivot de Gauss (le truc avec les conbinaisons de ligne)
\item[2] Comatrice 
\end{itemize}

M = $\begin{pmatrix}
a & e & g \\ 
b & d & h \\ 
c & f & i
\end{pmatrix} $
on pose $Cof_{i,j}(M)$ déterminant de la matrice dont on supprime la ieme ligne et j-eme colonne 


On pose $C_0$= $\begin{pmatrix}

2 & 8 & 4 \\ 
20 & 17 & 9 \\ 
9 & 19 & 15
\end{pmatrix} $ et $comC_0$ = $\begin{pmatrix}
3 & -3 & 11\\
-17 & 21 & -20\\
4 & -19 & 9 
\end{pmatrix}$
M = $\begin{pmatrix}
a & e & g \\ 
b & d & h \\ 
c & f & i
\end{pmatrix} $
on pose $Cof_{i,j}(M)$ déterminant de la matrice dont on supprime la ieme ligne et j-eme colonne 

d'ou le 21 central de com$c_0$ = 17 (de $C_0$) det $\begin{pmatrix}
2 & 4 \\ 
9 & 15
\end{pmatrix} $ modulo 27 = 21\\\\

et $C_0^{-1} = 26 * ^tcomC_0 = \begin{pmatrix}
24 & 17 & 23 \\ 
3 & 6 & 19 \\ 
16 & 20 & 18
\end{pmatrix} $\\

on sais que la clé de déchiffrement $K^{-1} = M_0.C_0^{-1}$
car \\$C_0 = K.M_0$\\
$K^{-1}.C_0 = K^{-1}.K.M_0=M_0$\\

\paragraph{EXO 7}
"{M}$_A$ : message M chiffré avec la clé A\\
A -> B : {M}A\\
B -> A : {{M}A}B\\
Alice recoit {{M}A}B , elle applique A-1, et retrouve {M}B\\
A -> B : {M}B\\
donc bob applique B-1 et retrouve M\\\\
\textbf{on utilise XOR} $K_A$ et $K_B$ les clés d'alice et bob\\
${M}_K = M \oplus K$\\
A -> B : $M \oplus K_A$\\
B -> A : $(M \oplus K_A) \oplus K_B = M \oplus K_A \oplus K_B$\\
Alice calcule $(M\oplus K_A \oplus K_B) \oplus K_A = M \oplus K_B$\\
A -> B : $M \oplus K_B$

\paragraph{EXO 7 Q3}
l'intrus ne connaît pas $K_A$ ou $K_B$ mais il intercepte TOUT ce qui passe sur le réseau\\
il intercepte 
\begin{itemize}
\item $I_1 = A->B : M \oplus K_A$
\item $I_2 = B->A : M\oplus K_A \oplus K_B$
\item $I_3 = A->B : M\oplus K_B$
\end{itemize}
On constate que si on fais un XOR global , on recupere direct le Message et donc facilement les clés aussi
\paragraph{EXO 7 Q4}
On utilise un chiffrement incassable.\\L'intrus est actif, il peut intercepter , bloquer, et emettre des messages\\On va noter I l'intrus et I(B) l'intrus qui se fait passer pour bob\\

\paragraph{EXO7 Q5} \textbf{peut on securiser le protocol} ?\\
IL faudrait un mécanisme d'authentification, de telle sorte à ce que 'intrus ne puisse se faire passer pour bob auprès d'alice
\section{TD1'}
\subsection{Feuille 1}
\paragraph{EXO1}
$Z/nZ$  = {0,...,n-1} avec l'addition et la multiplication modulo n\\
on note l'ensemble des éléments inversible pour X mod n est noté (Z/nZ)*\\
$x \in (Z/nZ)^* <=>pgcd(n,x) = 1$\\
par exemple en base 26 $(Z/26Z)* =${tous les impairs entre 0 et 25 sauf 13}\\
on va travailler dnas (Z/nZ)* avec la multiplication mod n.\\
on va fixer le n.\\
on va $g\in (Z/nZ)*$ un générateur :  $\forall x \in (Z/nZ)*, \exists k, g^k = x$\\
donc tous les éléments de (Z/nZ)* peuvent etre vu comme des puissances de g\\

\paragraph{PROBLEME DU LOGARITHME DISCRET}
on connais n et g\\
on nous donne $y \in (Z/nZ)*$\\
on sais qu'il existe x tel que y= $g^x$\\
le problème est de calculer x.

\paragraph{EXO 1 Q1}
KA = $y_B^a$ = $(g^b)^a$ = $g^{ab}$
KB = $y_A^b = (g^a)^b = g^{ab}$
donc $K_A=K_B$

\paragraph{EXO1 Q2}
n= 127 et g = 23\\
sur feuille
\paragraph{EXO1 Q3}
Si on sais résoudre DLP efficacement, l'intrus vois passer $y_a$et$y_b$ , il peut donc retrouver efficacement les valeurs a et b et calculer la clé qui crypte le message $K=g^{ab}$

\paragraph{EXO2 Q1}
a = $g^k$ , b=$h^k.m$
$a^x = g^{kx}$ , b $ =g^{kx}.m$
m = $b.a^{-x}$\\
Donc bob calcul $a^{-x}b$ pour retrouver m.

\section{TD2}
\subsection{Exo1}
\paragraph{Question 2}dans toute la suite , on connais $l_0,r_0,l_2,r_2,f$\\
on veux retrouver la clé $k$
$\begin{pmatrix}
l_1 = r_0 & l_1 = r_2 \oplus f(l_2,k_2) \\ 
r_1 = f(r_0,k_1) \oplus l_0 & r_1=l_2
\end{pmatrix} $\\
$\begin{array}{c}
r_0 = r_2 \oplus f(l_2k_2) \\ 
l_2 = f(r_0,k_1)\oplus l_0
\end{array} $\\
$\begin{array}{c}
L_2R_2 = 1011 \\ 
L_0R_0 = 0001
\end{array} $

\subsection{Exo 4}
\paragraph{•}


\subsection{Exo2}
\paragraph{Diffusion} rendre complexe la relation entre le texte chiffré et le texte clair
\paragraph{Confusion} rendre complexe la relation entre le texte chiffré et la clé
\paragraph{Exemples}
\begin{itemize}
\item[ECB] diffusion pas terrible car bloc texte clair égal bloc texte chiffré
\item[CBC] meilleure diffusion car un bloc chiffré dépende de tous les blocs clairs précédents
\item[Exo1] fonction linéaire, mauvaise confusion car on retrouve facilement la clé
\item[Fonction f non-linéaire] meilleure confusion, car il n'est pas toujours possible de retrouver la clé
\item[Feistel/DES] échange gauche/droite des blocs , tendance à mélanger et à augmenter la diffusion, et nous avons des S/E-box pour augmenter la confusion, car ça étend la clé, et modifie des bits pour qu'elle ne soit pas facile à retrouver
\end{itemize} 
\end{document}